Since New Approach to Multi-Objective A ^* combined with dimensionality reduction technique (NAMOA _dr ^*) algorithm has the phenomenon of plateau exploration, a Random Walk assisted NAMOA _dr ^* (RWNAMOA _dr ^*) algorithm which invoked a random walk procedure was proposed to find an exit (labels with heuristic value not dominated by the last extended label's) when the NAMOA _dr ^*was stuck on a plateau. To determine when NAMOA _dr ^* algorithm was stuck on a plateau exploration, a method of detecting plateau exploration was proposed. When the heuristic value of the extended label was dominated by the last extended label's for continuous m times, NAMOA _dr ^* algorithm was considered to fall into the plateau exploration. In the experiments, a randomly generated grid was used, which was a standard test platform for the evaluation of multi-objective search algorithms. The experimental results reveal that compared with NAMOA _dr ^* algorithm, RWNAMOA _dr ^* algorithm's running time is reduced by 50.69% averagely and its space consuming is reduced by about 10% averagely, which can provide theoretical support for accelerating multi-objective path searching in real life.